package kyssion.leetcode.num1_50;

/**
 * 给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
 * <p>
 * 示例 1:
 * <p>
 * 输入: "(()"
 * 输出: 2
 * 解释: 最长有效括号子串为 "()"
 * 示例 2:
 * <p>
 * 输入: ")()())"
 * 输出: 4
 * 解释: 最长有效括号子串为 "()()"
 */
public class code32_最长有效括号 {
    public static void main(String[] args) {
        System.out.println(new code32_最长有效括号().longestValidParentheses3("(()"));
    }

    /**
     * 方法1 消除法 这个不说了
     *
     * @param s
     * @return
     */
    public int longestValidParentheses(String s) {
        char[] item = s.toCharArray();
        int sped = 0;
        int[] befIndex = new int[item.length];
        for (int a = 0; a < item.length; a++) {
            if (item[a] == '(') {
                befIndex[sped] = a;
                sped++;
                continue;
            }
            if (sped > 0) {
                item[befIndex[sped - 1]] = item[a] = '*';
                sped--;
            } else {
                sped = 0;
            }
        }
        int maxResult = 0;
        int result = 0;
        for (int a = 0; a < item.length; a++) {
            if (item[a] == '*') {
                result++;
            } else {
                maxResult = Math.max(maxResult, result);
                result = 0;
            }
        }
        return Math.max(maxResult, result);
    }

    /**
     * 方法2
     * 好想法啊,第一个for循环能解决所有(数量大于)数量的完美匹配,比如(((()()
     * 第二for循环解决所有)大于( 的完美匹配 比如 ()())))))
     * 这种括号一共就只有这两种情况
     * (() 其实就是 ()) 倒过来的样子,思维要灵活啊
     *
     * @param s
     * @return
     */
    public int longestValidParentheses2(String s) {
        int left = 0, right = 0;
        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                result = Math.max(result, left * 2);
            }
            if (right > left) {
                left = right = 0;
            }

        }
        left = right = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                result = Math.max(result, left * 2);
            }
            if (right < left) {
                left = right = 0;
            }

        }
        return result;
    }

    /**
     * 最后一种动态规划 ,规划表达式
     * dp[i]=dp[i-1]+2+dp[i-dp[i-1]+2]
     * 如果dp[i]的值是4 表面之前的4个都是
     * @param s
     * @return
     */

    public int longestValidParentheses3(String s) {
        char[] item = s.toCharArray();
        int[] dp = new int[item.length + 1];
        dp[0] = 0;
        int num = 0;
        int ans = 0;
        for (int a = 0; a < item.length; a++) {
            if (item[a] == '(') {
                num++;
                continue;
            }
            if (num > 0) {
                num--;
                dp[a] = dp[a - 1] + 2;
            }
            if (a > dp[a]) {
                dp[a] += dp[a - dp[a]];
            }
            ans = Math.max(dp[a], ans);
        }
        return ans;
    }
}
